using System;
using System.Collections.Generic;
using System.Text;

public class BinarySearchTree<T> : ICloneable where T : IComparable<T>
{
    private int count = 0;
    private Tree<T> root = new Tree<T>(default(T));
    private List<T> listHolder;

    public override int GetHashCode()
    {
        unchecked
        {
            int result = 17;
            result = result * 23 + ToList().GetHashCode();
            return result;
        }
    }

    public int Count
    {
        get
        {
            return count;
        }
    }

    public void Add(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException("You cant pass null value to Add method.");
        }
        if (count == 0)
        {
            root = new Tree<T>(value);
        }
        else
        {
            Tree<T> vertexToInsert = new Tree<T>(value);
            Tree<T> iterator = root;
            while (true)
            {
                int compareResult = iterator.Value.CompareTo(vertexToInsert.Value);
                if (compareResult > 0)
                {
                    if (iterator.LeftChild == null)
                    {
                        iterator.LeftChild = vertexToInsert;
                        vertexToInsert.Parent = iterator;
                        break;
                    }
                    else
                    {
                        iterator = iterator.LeftChild;
                    }
                }
                else if (compareResult < 0)
                {
                    if (iterator.RightChild == null)
                    {
                        iterator.RightChild = vertexToInsert;
                        vertexToInsert.Parent = iterator;
                        break;
                    }
                    else
                    {
                        iterator = iterator.RightChild;
                    }
                }
                else
                {
                    InsertIfEquivalent(vertexToInsert, iterator);
                    break;
                }
            }
        }
        count++;
    }

    private static void InsertIfEquivalent(Tree<T> vertexToInsert, Tree<T> iterator)
    {
        //we need to isert it as rightChild of the Iterator
        while (iterator.RightChild != null &&
               iterator.RightChild.Value.Equals(vertexToInsert.Value))
        {
            iterator = iterator.RightChild;
        }

        vertexToInsert.RightChild = iterator.RightChild;
        iterator.RightChild = vertexToInsert;
        vertexToInsert.Parent = iterator;
    }

    public bool RemoveElement(T valueToRemove)
    {
        Tree<T> vertexToDelete = Find(valueToRemove);
        if (vertexToDelete == null)
        {
            return false;
        }
        RemoveVertex(vertexToDelete);
        return true;
    }

    private void RemoveVertex(Tree<T> vertexToDelete)
    {
        if (vertexToDelete.LeftChild != null && vertexToDelete.RightChild != null)
        {
            Tree<T> replacement = vertexToDelete.RightChild;
            while (replacement.LeftChild != null)
            {
                replacement = replacement.LeftChild;
            }
            vertexToDelete.Value = replacement.Value;
            vertexToDelete = replacement;
        }

        Tree<T> theChild = vertexToDelete.LeftChild != null ?
                           vertexToDelete.LeftChild : vertexToDelete.RightChild;

        if (theChild != null)
        {
            theChild.Parent = vertexToDelete.Parent;

            if (vertexToDelete.Parent == null)
            {
                root = theChild;
            }
            else
            {
                if (vertexToDelete.Parent.LeftChild == vertexToDelete)
                {
                    vertexToDelete.Parent.LeftChild = theChild;
                }
                else
                {
                    vertexToDelete.Parent.RightChild = theChild;
                }
            }
        }
        else
        {
            if (vertexToDelete.Parent == null)
            {
                root = null;
            }
            else
            {
                if (vertexToDelete.Parent.LeftChild == vertexToDelete)
                {
                    vertexToDelete.Parent.LeftChild = null;
                }
                else
                {
                    vertexToDelete.Parent.RightChild = null;
                }
            }
        }
    }

    public bool Contains(T value)
    {
        Tree<T> found = Find(value);
        return found != null;
    }

    private Tree<T> Find(T value)
    {
        Tree<T> iteratorNode = this.root;

        while (iteratorNode != null)
        {
            int compareTo = value.CompareTo(iteratorNode.Value);
            if (compareTo < 0)
            {
                iteratorNode = iteratorNode.LeftChild;
            }
            else if (compareTo > 0)
            {
                iteratorNode = iteratorNode.RightChild;
            }
            else
            {
                break;
            }
        }
        return iteratorNode;
    }

    public override string ToString()
    {
        StringBuilder result = new StringBuilder();
        ToList().ForEach(x => result.Append(string.Format("{0} ", x.ToString())));
        return result.ToString();
    }

    public void VisualRepresentationOnConsole()
    {
        PrintOut(root, string.Empty);
    }

    private void PrintOut(Tree<T> iterator, string spaces)
    {
        if (iterator.LeftChild != null)
        {
            PrintOut(iterator.LeftChild, spaces + " ");
        }
        Console.WriteLine("{0} {1}", spaces, iterator.Value);
        if (iterator.RightChild != null)
        {
            PrintOut(iterator.RightChild, spaces + " ");
        }
    }

    public List<T> ToList()
    {
        listHolder = new List<T>();
        Traverse(root);
        return listHolder;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is BinarySearchTree<T>))
        {
            return false;
        }

        BinarySearchTree<T> other = (BinarySearchTree<T>)obj;
        var otherList = other.ToList();
        var thisList = ToList();

        if (thisList.Count != otherList.Count)
        {
            return false;
        }
        for (int index = 0; index < thisList.Count; index++)
        {
            if (!thisList[index].Equals(otherList[index]))
            {
                return false;
            }
        }
        return true;
    }

    private void Traverse(Tree<T> iterator)
    {
        if (iterator.LeftChild != null)
        {
            Traverse(iterator.LeftChild);
        }
        listHolder.Add(iterator.Value);
        if (iterator.RightChild != null)
        {
            Traverse(iterator.RightChild);
        }
    }

    public static bool operator ==(BinarySearchTree<T> one, BinarySearchTree<T> two)
    {
        return one.Equals(two);
    }

    public static bool operator !=(BinarySearchTree<T> one, BinarySearchTree<T> two)
    {
        return !one.Equals(two);
    }

    /// <summary>
    /// The result is fair balanced BinarySearchTree Deep Copy.
    /// </summary>
    /// <returns></returns>
    public object Clone()
    {
        BinarySearchTree<T> deepCopy = new BinarySearchTree<T>();
        sortedArrayToBST(deepCopy, ToList(), 0, count);
        return deepCopy as object;
    }

    private void sortedArrayToBST(BinarySearchTree<T> deepCopy, List<T> array, int start, int end)
    {
        if (start > end || start == count)
        {
            return;
        }
        int mid = start + (end - start) / 2;
        deepCopy.Add(array[mid]);
        sortedArrayToBST(deepCopy, array, start, mid - 1);
        sortedArrayToBST(deepCopy, array, mid + 1, end);
    }
}